package problem;


import instance.InstanceResultado;
import instance.InstanceTP3;

import java.util.Iterator;
import java.util.LinkedList;
import java.lang.System;

public class Exacto {
	public static int contador_Exacto;
	public static int pes_mejor_solucion;
	
	private int res;

	private boolean[] vector_visitados;
	private Integer[] vector_solucion ;
	private int cant_nodos;
	private int nodo_origen;
	private int cant_ciclos;
	private Integer[] solucion_final;
	
	//version 2
	private int pesoHastaElMomento;
	private int[][] matriz;
	private boolean noTengoUnaSolucion;
	///version 2
	
	public Exacto(InstanceTP3 instance){
		//creo el vector que indicara que nodos ya revise y que nodos no
		int cant_nodos = instance.n;
		int nodo_origen = instance.nodo_origen;
		vector_visitados = new boolean[cant_nodos];
		//creo el vector que va a representar que nodo se conecta con otro en el recorrido de los 2 ciclos
		vector_solucion = new Integer[cant_nodos+1];
		//inicializo los vectores
		for(int i=0; i<cant_nodos; i++){
			vector_visitados[i] = false;
			vector_solucion[i] = -1;
		}
		///version modificada para el rtp3
		//asigno la matriz que viene con la instance
		this.matriz = instance.matriz; 
		//asigno true para decir que todavia no forme una solucion
		this.noTengoUnaSolucion = true;
		//el peso inicial es 0
		this.pesoHastaElMomento = 0;
		this.solucion_final = new Integer[cant_nodos+1];
		///version modificada para el rtp3
		
		//pongo al nodo origen como ya visitado
		vector_visitados[nodo_origen] = true;
		//seteo la cantidad de nodos
		this.cant_nodos = cant_nodos;
		//seteo el nodo origen
		this.nodo_origen = nodo_origen;
		//seteo la cantidad de ciclos
		this.cant_ciclos = 0;
		busca_ciclos_recursiva(vector_visitados, vector_solucion, nodo_origen , this.cant_ciclos, 1);
		//aca ya deberia tener en res el peso de la mejor solucion del problema	
	}
	
	public void mostrar(Integer[] solucion, int[][] matriz_de_pesos){
		System.out.println("El origen es: " +nodo_origen );
		System.out.println("La cantidad de nodos es: " + cant_nodos);
		
		int nodin = solucion[nodo_origen];
		boolean es_segundo_ciclo = false;
		boolean no_termine = true;
		int nodo_de_donde_vengo = nodo_origen;
		System.out.print(nodo_origen+" -- ["+ matriz_de_pesos[nodin][nodo_de_donde_vengo] + "] --");
		while(no_termine){
			if(!es_segundo_ciclo){
				if(nodin == nodo_origen){
					System.out.print(nodin);
					nodo_de_donde_vengo = nodin;
					nodin = solucion[cant_nodos];
					System.out.print(" -- ["+ matriz_de_pesos[nodin][nodo_de_donde_vengo] + "] --" );
					es_segundo_ciclo = true;
				}else{
					System.out.print(nodin);
					nodo_de_donde_vengo = nodin;
					nodin = solucion[nodin];
					System.out.print(" -- ["+ matriz_de_pesos[nodin][nodo_de_donde_vengo] + "] --" );
					
				}
			}else{
				if(nodin == nodo_origen){
					System.out.println(nodin);
					System.out.print("Fin ");
					no_termine = false;
				}else{
					System.out.print(nodin);
					nodo_de_donde_vengo = nodin;
					nodin = solucion[nodin];
					System.out.print(" -- ["+ matriz_de_pesos[nodin][nodo_de_donde_vengo] + "] --" );
					
				}
			}
		}
	}
	
	public void busca_ciclos_recursiva(boolean[] vector_visitados, Integer[] vector_solucion, int nodo_actual , int ciclos_armados, int cantidad_revisados){
		//al nodo donde estoy parado lo marco como visitado
		vector_visitados[nodo_actual] = true;
		for(int i=0; i < this.cant_nodos ; i++){
			//version modificada para el rtp3:
			//aca esta la poda:
			//si no me pase del mejor peso que consegui hasta el momento si voy desde el nodo actual al nodo i 
			if(this.pesoHastaElMomento+ this.matriz[nodo_actual][i] < res || this.noTengoUnaSolucion){
			//version modificada para el rtp3
				//si no revise el nodo i
				if(!vector_visitados[i]){
					//si esta es la 2da vez que salgo del nodo origen => guardo en otra posicion el lugar a donde voy
					if(ciclos_armados == 1 && nodo_actual == this.nodo_origen){
						vector_solucion[this.cant_nodos] =  new Integer(i);
						//version modificada para el rtp3:
						this.pesoHastaElMomento+= this.matriz[nodo_actual][i];
						busca_ciclos_recursiva(vector_visitados, vector_solucion, i, ciclos_armados, cantidad_revisados+1);
						this.pesoHastaElMomento = this.pesoHastaElMomento - this.matriz[nodo_actual][i];
						//version modificada para el rtp3
						vector_solucion[this.cant_nodos] = -1;
					}else {
						vector_solucion[nodo_actual] = new Integer(i);
						//version modificada para el rtp3:
						this.pesoHastaElMomento+= this.matriz[nodo_actual][i];
						busca_ciclos_recursiva(vector_visitados, vector_solucion, i, ciclos_armados, cantidad_revisados+1);
						this.pesoHastaElMomento-= this.matriz[nodo_actual][i];
						//version modificada para el rtp3
						vector_solucion[nodo_actual] = -1;
					}
					vector_visitados[i]= false;
				} else {
					//si estoy formando un ciclo con el nodo_origen
					if(i == nodo_origen && nodo_actual != nodo_origen){
						//si es el primer ciclo que voy a armar
						if(ciclos_armados==0 && cantidad_revisados <= this.cant_nodos-2 && cantidad_revisados > 2){
							int tmp = vector_solucion[nodo_actual].intValue();
							vector_solucion[nodo_actual] = new Integer(i); // lo pongo en una posicion especial porque me cierra el primer ciclo
							//version modificada para el rtp3:
							this.pesoHastaElMomento+= this.matriz[nodo_actual][i];
							busca_ciclos_recursiva(vector_visitados, vector_solucion, i, ciclos_armados+1, cantidad_revisados);
							this.pesoHastaElMomento-= this.matriz[nodo_actual][i];
							//version modificada para el rtp3
							vector_solucion[nodo_actual] = new Integer(tmp);
						}else{
							//si ya tenia un ciclo armado entonces estoy cerrando otro ahora
							if(ciclos_armados==1 && cantidad_revisados == this.cant_nodos){
								//version modificada para el rtp3:
								//si llego hasta este caso entonces esta solucion pesa menos que la que tenia
								//guardo la solucion(el camino que arme):
								for(int j=0; j<this.cant_nodos+1; j++){
									this.solucion_final[j] = vector_solucion[j];
								}
								this.noTengoUnaSolucion = false;
								this.res = this.pesoHastaElMomento + this.matriz[nodo_actual][i];
								//version modificada para el rtp3
							}
						}
					}
				}
			}
		}
	
	}


	public boolean[] getVector_visitados() {
		return vector_visitados;
	}

	public Integer[] getVector_solucion() {
		return vector_solucion;
	}

	public Integer[] getSolucionFinal(){
		return solucion_final;
	}
	
	
	public InstanceResultado getRes() {
		//DEVUELVE LA SOLUCIÓN ESPERADA POR OUTPUT: ignora al nodo origen y los nodos van desde 1 hasta n
		InstanceResultado insres = new InstanceResultado();
		int nodin = solucion_final[nodo_origen];
		boolean es_segundo_ciclo = false;
		boolean no_termine = true;
		int nodo_de_donde_vengo = nodo_origen;
		while(no_termine){
			if(!es_segundo_ciclo){
				if(nodin == nodo_origen){
					nodo_de_donde_vengo = nodin;
					nodin = solucion_final[cant_nodos];
					es_segundo_ciclo = true;
				}else{
					insres.getPrimer_ciclo().add(nodin);
					nodo_de_donde_vengo = nodin;
					nodin = solucion_final[nodin];
				}
			}else{
				if(nodin == nodo_origen){
					no_termine = false;
				}else{
					insres.getSegundo_ciclo().add(nodin);
					nodo_de_donde_vengo = nodin;
					nodin = solucion_final[nodin];
				}
			}
		}
		insres.setNodo_origen(nodo_origen);
		nodin = solucion_final[nodo_de_donde_vengo];// Para sacarme de encima un warning molesto.	NO tiene efecto alguno esta línea
		return insres;
	}
	public int getResFinal() {
		return res;
	}
}